import java.util.Objects;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-02-21
 * Time: 21:11
 */


public class HashBucket2<K,V> {
    // 定义哈希桶结点
    static class Node<K,V> {
        public K key;
        public V value;
        public Node<K,V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    // 创建哈希表，初始容量为 10
    public Node<K,V>[] hashTable = (Node<K, V>[]) new Node[10];// (这种方式虽然报警告，但是它是正确的)
    // 哈希表中有效元素个数
    public int usedSize;

    // 负载因子，此处取0.75（负载因子 = 填入表中元素个数/散列表长度）
    public static final double LOAD_FACTOR = 0.75;

    // (1)calculate_LoadFactor():计算此时负载因子
    private double calculate_LoadFactor() {
        return usedSize * 1.0 / hashTable.length;
    }

    // (2)resize():扩容并重新计算哈希值和位置，并存储到新的哈希表中。
    private void resize() {
        // 扩容
        Node<K,V>[] newhashTable = (Node<K, V>[]) new Node[2* hashTable.length];
        // 因为改变了散列表长度，需要重新将每一个结点散列到新的位置
        for (int i = 0; i < hashTable.length; i++) {
            Node<K,V> cur = hashTable[i];
            while (cur != null) {
                // 记录curNext的位置，防止后续调整丢失
                Node<K,V> curNext = cur.next;
                // 重新计算哈希值
                int hash = cur.key.hashCode() & Integer.MAX_VALUE;
                // 根据散列函数计算散列位置
                int index = hash % newhashTable.length;
                // 头插法
                cur.next = newhashTable[index];
                newhashTable[index] = cur;
                cur = curNext;
            }
        }
        // 更新哈希表
        hashTable = newhashTable;
    }

    // 1.put(K key,V value):插入操作
    public void put(K key,V value) {
        // 计算 key 值的 hash 值
        int hash = key.hashCode() & Integer.MAX_VALUE;
        // 取留余数法
        int index = hash % hashTable.length;

        Node<K,V> cur = hashTable[index];
        // 判断是否已经存在key值（哈希表中不允许存在相同key值）
        while (cur != null) {
            if (cur.key.equals(key)) {
                // 如果存在 key 相同的元素，更新 value 值
                cur.value = value;
                return;
            }
            cur = cur.next;
        }

        // 采用头插法
        Node<K,V> newNode = new Node<>(key, value);
        newNode.next = hashTable[index];
        hashTable[index] = newNode;
        usedSize++;

        // 为减少冲突率，我们要判断负载因子是否超过预设值
        if (calculate_LoadFactor() >= LOAD_FACTOR) {
            // 如果大于等于负载因子，需要扩容
            resize();
        }

    }

    // 2.get(K key):查询
    public V get(K key) {
        // 计算哈希值
        int hash = key.hashCode() & Integer.MAX_VALUE;
        // 根据散列函数计算散列位置
        int index = hash % hashTable.length;
        // 遍历哈希桶，寻找元素
        Node<K,V> cur = hashTable[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                // 找到返回 值value
                return cur.value;
            }
            cur = cur.next;
        }
        // 找不到返回 null
        return null;
    }
}
